#include <iostream>

using namespace std;
#include "LinkedList.h"
#include <sstream>




// CONSTRUCTOR - DESTRUCTOR
//default constructor initializes variables so that the list looks empty
LinkedList::LinkedList():firstNode(NULL),lastNode(NULL),Size(0),useDebug(false)
{
}

//destructor
LinkedList::~LinkedList()
{
	//we just clear all our nodes before dying
	if(useDebug)
		cout << "destructor LinkedList object" << this << endl;
	if(useDebug) cout << "how it is before clearing:" << this <<endl;
	if(useDebug) print();
	clear();
	if(useDebug)
		cout << "end of destructor" << endl;

}

//copy constructor
LinkedList::LinkedList(Collection* other):Collection(other),firstNode(NULL),lastNode(NULL),Size(0),useDebug(false)
{
	if(other != this)
		//copy all the elements from other into ourself
		addAll(other);
	else
		cout << "LinkedList::LinkedList(Collection*) cannot copy elements from oneself! Giving up."<<endl;
}

LinkedList& LinkedList::operator=(LinkedList& other)
{
	LinkedList* wontDisappear = new LinkedList();
	wontDisappear->addAll(&other);
	return *wontDisappear;
}

void LinkedList::enableDebug()
{
	useDebug = true;
	cout << "<LinkedList object at "<<this<<">:Debug enabled</LinkedList>" <<endl;
}

void LinkedList::disableDebug()
{
	useDebug = false;
	cout << "<LinkedList object at "<<this<<">:Debug disabled</LinkedList>" <<endl;
}

// READING THINGS FROM THE LIST
bool LinkedList::isEmpty() const
{
	return Size == 0;
}

int LinkedList::size() const
{
	return Size;
}

// MODIFYING THE LIST
//clear the list of all its elements (all of them erased)
void LinkedList::clear()
{
	Node* nxt;
	Node* now;
	int a;
	
	if(!isEmpty())
	{
		now = firstNode;
		//clear all the elements
		for(a=0;a<size();a++)
		{
			//Remove this when code is trustable
			//this is because we don't do pointer checking and only rely on integers...
			//just in case there was some Size assignment had not been done somewhere in the code
			if(now==NULL)
			{
				throw LinkedListException("DEBUG:shouldn't have now==NULL this in LinkedList::clear()"); //keep independent of if(useDebug) !!!
			}
			nxt = now->getNext();
			delete now;
			now = nxt;
		}
		//now set the list as empty
		Size = 0;
		firstNode = lastNode = NULL;
	}
	else if(useDebug)
		cout << "LinkedList::clear() list is already empty, nothing done." << endl;
}

//returns the node at INDEX or NULL if index is not correct or list empty
Node* LinkedList::nodeAt(int index)
{
	int a;
	Node* now=firstNode;
	Node* result=NULL;
	//if list is not empty and given index is in the correct range
	if(Size > 0 && (index >= 0 && index < Size))
	{
		//thanks to a for loop, attain the element whose index is equal to given INDEX
		//(note: before the loop, the current element NOW corresponds to element of index 0)
		for(a=0;a<index;a++) //note : don't go till a==index since now=now->getNext() has one step in advance (firstNode assignation at the beginning)
			now = now->getNext();
		//the index of NOW is now worth INDEX
		if(useDebug)
			if(index != a) cout << "Node* LinkedList::nodeAt(int index) check the for loop reached index is "<<a<<" while it should be "<<index;
		
		result = now;
	}
	//if list empty or given index out of range
	else
	{
		string yo="LinkedList.nodeAt (";
		char hop [5];
		sprintf(hop,"%d",index);
		yo+=hop;
		yo+="): index out of range or list empty";
		throw LinkedListException(yo);
		result = NULL;
	}
	return result;
}

//adds an element with value VALUE to the end of the list
void LinkedList::add(int value)
{
	Node* tmp = new Node(value,NULL);
	//if there already are elements in the list
	if(lastNode != NULL)
	{
		lastNode->setNext(tmp);
		lastNode = lastNode->getNext(); //set to point the new last node
	}
	else//if we're adding the very first element in the list
		firstNode = lastNode = tmp;
	Size++;
}

//inserts element with value ELEMENT at position INDEX in the list
//this shifts elements if needed
void LinkedList::add(int index,int element)
{
	Node* next;
	Node* prev;
	Node* newone;
	if(index >= 0 && index <= size()) //note we can insert something as the last element with linkedlist.add(linkedlist.size(),3)
	{
		newone = new Node(element,NULL);
		//if we are to told to insert something at the beginning
		if(index==0)
		{
			if(useDebug) cout << "DEBUG:adding at the beginning"<<endl;
			newone->setNext(firstNode); //set ourself to have our next element be to the element we're shifting away
			firstNode = newone; //the first element is now us
			if(Size==0) lastNode = firstNode; //if there's going to be only one element after this insertion, last and first node must point to this element
		}
		//if we are to told to insert something after the last element (at the end)
		else if(index==size())
		{
			if(useDebug) cout << "DEBUG:adding at the end"<<endl;
			newone->setNext(NULL); //no Node after us
			lastNode->setNext(newone);
			lastNode = newone;
			
		}
		//if we are told to insert something in the middle of the list
		else
		{
			if(useDebug) cout << "DEBUG:adding in the middle" << endl;
			prev = nodeAt(index-1); //the Node before the one with the given index (note:index-1 is necessarily in the correct range because the previous if's)
			next = nodeAt(index); //the Node after the one with the given index
			prev->setNext(newone);
			newone->setNext(next);
		}
		Size++;
	}
	else
		cout << "void LinkedList::add(int index,int element): index:"<<index<<" out of range (max is size()="<<size()<<"."<<endl;
}

//adds all the elements of the other list into ourselves
void LinkedList::addAll(Collection* c)
{
	int a;
	if(c!=NULL)
	{
		//we don't want any recursion so as not to fall into an infinite loop
		if(c==this)
		{
			throw LinkedListException("ERROR:LinkedList::addAll(Collection*): cannot add elements of oneself! Giving up.");
		}
		else
		{	//add all the elements of the other list into ourselves
			for(a=0;a<c->size();a++)
			{
				this->add(c->get(a));
			}
		}
	}
}
   
// Inserts all of the elements in the specified collection into this
// collection at the specified position
void LinkedList::addAll(int index, Collection* c)
{
	int a;
	int initialSize;
	if(c!=NULL)
	{
		if(index >= 0 && index <= size())
		{
			initialSize = c->size();
			for(a=0;a<initialSize;a++)
			{
				if(useDebug) cout << "DEBUG:addAll(int,Collection*): adding at index:"<<index<< " when size()=" << size() << endl;
				add(index,c->get(a));
				index ++;
			}
		}
		else
			cout << "void LinkedList::addAll(int index,Collection*): index:"<<index<<" out of range (max is size()="<<size()<<"."<<endl;
	}
	else
		cout << "void LinkedList::addAll(int index,int element): given collection is NULL."<<endl;
}
   
   
   // Returns true if this collection contains the specified element.
bool LinkedList::contains(int element)
{
	return search(element) >= 0;
}
   
   // Returns the element at the specified position in this collection.
int LinkedList::get(int index)
{
	Node* elem;
	try
	{
		elem = nodeAt(index);
	}
	catch(LinkedListException e)
	{
		throw e;
		return -1;
	}
	if(elem) //if the node at the given index is not NULL (exists)
	{
		return elem->getValue();
	}
	else
	{
// 		ostringstream o;
// 		o << "LinkedList::get(index="<<index<<") nothing at given index => returned -1";
// 		cout << "I will throw " << o.str() << endl;
// 		throw LinkedListException(o.str());
		return -1;
	}
}
   
   
   // Removes the element at the specified position in this collection
void LinkedList::remove(int index)
{
	Node* tmp;
	Node* tmp2;
	if(index >=0 && index < size()) //if index is in the correct range
	{
		//if node to remove is the first of the list
		if(index == 0)
		{
			//set the first node to the one actually after
			//and free the node that was the first node
			tmp = firstNode;
			firstNode = firstNode->getNext();
			delete tmp;
		}
		//if node to remove is the last of the list
		else if(index == size()-1)
		{
			tmp = nodeAt(size()-2); //node before the last one
			tmp->setNext(NULL); //say there's nothing after the node to become last
			delete lastNode; //delete what was at the last node
			lastNode = tmp; //set the new last node to be the node before the previous last node
		}
		//if we delete something in the middle
		else
		{
			tmp = nodeAt(index); //the node to remove
			tmp2 = nodeAt(index-1); //the node before the one remove
			tmp2->setNext(tmp->getNext()); //set the previous node to point to the node after that to remove
			delete tmp;//free the node to remove from memory
		}
		Size--;
		if(Size == 0) firstNode = lastNode = NULL;
	}
	else
	{
		ostringstream o;
		o<<"LinkedList::remove(index="<<index<<") : index out of range => nothing removed ";
		throw LinkedListException(o.str());
	}
}

//returns the index of an element in the list or -1 if element not found
int LinkedList::search(int element)
{
	int a;
	for(a=0;a<size();a++)
	{
		if(get(a) == element)
		{
			return a;
		}
	}
	return -1;
}

   // Removes from this collection all the elements that are contained in the
   // specified collection
void LinkedList::removeAll(Collection* c)
{
	int a;
	int posFound;
	int count=0;
	if(c!=NULL)
	{
		//we don't want any recursion so as not to have a crash
		if(c==this)
		{
			throw LinkedListException("ERROR:LinkedList::removeAll(Collection*): cannot add elements of oneself! Giving up.");
		}
		//if no recursion test passed ok
		else
		{
			if(isEmpty())
			{
				if(useDebug)
					cout << "DEBUG:LinkedList::removeAll(Collection*): this is list empty => nothing removed."<<endl;
			}
			else
			{
				if(size() < c->size())
				{
					string yo1,yo2;
					char hop[100];
					sprintf(hop,"%d",c->size());
					yo1 += hop;
					sprintf(hop,"%d",c->size());
					yo2 += hop;
					
					throw LinkedListException("LinkedList::removeAll(Collection*): you're trying to remove a list with size()="+yo1+" from a list smaller than that with size()="+yo2+".");
				}
				for(a=0;a<c->size();a++)
				{
					//we choose to remove every single item (they can be several) found within the other collection from ourselves
					do
					{
						//if current element of the other collection exists in ourselves
						posFound = this->search(c->get(a));
						if(posFound >= 0) //if something found
							//delete this element from ourselves
						{
							this->remove(posFound);
							count++;
						}
					}while(posFound >=0);
				}
				if(useDebug)
				{
					if(count==0)
						cout << "DEBUG:LinkedList::removeAll(Collection*): this list has no elements in common with provided Collection object."<<endl;
					else
						cout << "DEBUG:LinkedList::removeAll(Collection*): removed "<<count<<" item(s)."<<endl;
				}
			}
		}	
	}
}
      
   // Returns an array containing all of the elements in this list in proper
   // sequence
   //note : to have the length of the returned array, that length is equal to LinkedList.size()
int* LinkedList::toArray()
{
	int a;
	int* returnedList;
	if(size() > 0)
	{
		returnedList = new int[size()];
		for(a=0;a<size();a++)
		{
			returnedList[a] = get(a);
		}
	}
	else //list was empty
	{
		returnedList = NULL;
	}
	return returnedList;
}

void LinkedList::print()
{
	int a;
	if(isEmpty())
	{
		cout << "<LinkedList instance at " << this << ">" << endl << "no items"<<endl;
	}
	else
	{
		cout << "<LinkedList instance at " << this << ">" << endl;
		for(a=0;a<Size;a++)
		{
			cout << get(a) << ";" << endl;
		}
	}
	cout << "</LinkedList>" << endl;
}
